package org.nowcoder.leetcode.DP;

/**
 * Title  : 62. Unique Paths
 * Source : https://leetcode.cn/problems/unique-paths/
 * Author : XrazYang
 * Date   : 2023-12-14
 */

public class LeetCode_62 {
    public int uniquePaths(int m, int n) {
        //1. 定义状态： paths(m)(n)表示(0,0)->(m,n)的所有路径
        int[][] paths = new int[m][n];

        //2. 初始状态
        for (int i = 0; i < n; i++) {
            paths[0][i] = 1;
        }
        for (int i = 0; i < m; i++) {
            paths[i][0] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //3. 状态转移方程
                paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
            }
        }
        return paths[m - 1][n - 1];
    }
}
